package test;


public class DeleteNode_O1_Time {

	/**
	 * Q 60 在O(1)时间删除链表结点
	 * 给定链表的头指针和一个结点指针(!!)，在O(1)时间删除该结点
	 * 
	 * Assume the list is:
	 * head->...->nodeToDelete->mNode->nNode->...->tail
	 * you have already the point of 'nodeToDelete' in hand.So what you need to do is:
	 * 1.copy the data of 'mNode' to 'nodeToDelete'
	 * 2.nodeToDelete.next=nNode;
	 * However,when deleting the last node,you have to iterate from 'head'.No shortcut.
	 * 
	 * ---public static void deleteNode(Node head,Node nodeToDelete){
	 * cannot do it like that.Because you cannot set head=null to make 'list' empty.
	 * see 'class ParameterTransfer'
	 */

	private static class List{
		private Node head;
		
		Node createList(int[] data){
			if(data==null||data.length==0){
				return null;
			}
			Node previous=null;
			for(int len=data.length,i=len-1;i>=0;i--){
				head=new Node(data[i]);
				head.next=previous;
				previous=head;
			}
			return head;
		}
		void printList(){
			Node node=head;//don't use 'head' immediately.It wastes my time to find the bug...
			while(node!=null){
				System.out.print(node.data+" ");
				node=node.next;
			}
			System.out.println();
		}
		Node getNodeAt(int pos){//starts from 0
			Node re=null;
			int index=0;
			Node node=head;
			while(node!=null){
				if(index==pos){
					return node;
				}
				node=node.next;
				index++;
			}
			return re;
		}
		
		
		void deleteNode(Node nodeToDelete){
			Node head=this.head;
			if(head==null||nodeToDelete==null){
				return;
			}
			if(head.next==null&&nodeToDelete==head){//Only one node in list and you happen to delete the node.
				head = null;
				return;
			}
			Node node=head;
			if(node.next!=null&&nodeToDelete!=null){
				Node mNode=nodeToDelete.next;
				if(mNode!=null){
					Node nNode=mNode.next;
					nodeToDelete.data=mNode.data;
					nodeToDelete.next=nNode;
				}else {//'nodeToDelete' is the last Node.
					Node previous=node;
					while(node.next!=null){
						previous=node;
						node=node.next;
					}
					previous.next=null;
					return;
				}
				
			}
		}
	}
	private static class Node{
		int data;
		Node next;
		Node(int data){
			this.data=data;
		}
	}
	
	public static void main(String[] args) {
		int[] data={0,1,2,3,4,5,6,7,8};
		List list=new List();
		list.createList(data);
		list.printList();
		
		Node nodeToDelete=list.getNodeAt(8);
		list.deleteNode(nodeToDelete);
		
		nodeToDelete=list.getNodeAt(3);
		list.deleteNode(nodeToDelete);
		
		nodeToDelete=list.getNodeAt(0);
		list.deleteNode(nodeToDelete);
		
		list.printList();//1 2 4 5 6 7
		
		list.createList(new int[]{1});
		list.deleteNode(list.getNodeAt(0));
		list.printList();//nothing.
		
	}
}


